package exhaustivity.buckets;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author longzj
 */
class BucketSolution {

    public static void main(String[] args) {
        BucketSolution solution = new BucketSolution();
        solution.printResult();
    }

    private Stack<BucketState> mTotalStates;
    private List<BucketState> mResultStates;

    private static final int MAX_INDEX = 3;
    private static final int INIT_MAX_VOLUME = 8;
    private static final int INIT_MID_VOLUME = 5;
    private static final int INIT_MIN_VOLUME = 3;
    private static final int RESULT_VOLUME = 4;

    private static final int[] VOLUMES = new int[]{
            INIT_MAX_VOLUME,
            INIT_MID_VOLUME,
            INIT_MIN_VOLUME,
    };

    BucketSolution() {
        mTotalStates = new Stack<>();
        mResultStates = new ArrayList<>();
    }

    void printResult() {
        final BucketState rootState = new BucketState(INIT_MAX_VOLUME, 0, 0);
        traverse(rootState);
        for (BucketState resultState : mResultStates) {
            getSolutionStr(resultState, new StringBuilder());
        }
    }

    private void getSolutionStr(BucketState state, StringBuilder builder) {
        String tmp = "[" + state.getLargeVolume() + "," + state.getMiddleVolume() + "," + state.getSmallVolume() + "," + "]";
        if (!isResult(state)) {
            tmp += "->";
        }
        builder.insert(0, tmp);
        if (state.getLargeVolume() == INIT_MAX_VOLUME) {
            System.out.println(builder.toString());
            return;
        }
        getSolutionStr(state.getParentState(), builder);
    }

    private void traverse(BucketState root) {
        boolean isResult = isResult(root);
        BucketState existState = getExistState(root);
        if (existState != null) {
            return;
        }
        if (isResult) {
            mResultStates.add(root);
            return;
        }
        mTotalStates.push(root);
        for (int index = 0; index < MAX_INDEX; index++) {
            int restVolume = VOLUMES[index] - root.getValue(index);
            if (restVolume == 0) {
                continue;
            }
            for (int nextIndex = 0; nextIndex < MAX_INDEX; nextIndex++) {
                if (index == nextIndex) {
                    continue;
                }
                int nextValue = root.getValue(nextIndex);
                int diff = nextValue > restVolume ? restVolume : nextValue;
                BucketState state = getChildState(root, nextIndex, index, diff);
                if (state != null) {
                    state.setParentState(root);
                    traverse(state);
                }
            }
        }
        mTotalStates.pop();
    }

    private BucketState getChildState(BucketState state, int from, int to, int value) {
        if (value == 0) {
            return null;
        }
        BucketState newState = new BucketState(state.getLargeVolume(),
                state.getMiddleVolume(), state.getSmallVolume());
        newState.setValue(from, state.getValue(from) - value);
        newState.setValue(to, state.getValue(to) + value);
        StateTransition transition = new StateTransition();
        transition.setFrom(from);
        transition.setTo(to);
        transition.setAmount(value);
        newState.setTransition(transition);
        return newState;
    }

    private BucketState getExistState(BucketState inputState) {
        for (BucketState state : mTotalStates) {
            boolean isEqual = state.getLargeVolume() == inputState.getLargeVolume()
                    && state.getMiddleVolume() == inputState.getMiddleVolume()
                    && state.getSmallVolume() == inputState.getSmallVolume();
            if (isEqual) {
                return state;
            }
        }
        return null;
    }

    private boolean isResult(BucketState inputState) {
        return RESULT_VOLUME == inputState.getLargeVolume()
                && RESULT_VOLUME == inputState.getMiddleVolume()
                && 0 == inputState.getSmallVolume();
    }

}
